package com.zdp.leetcodeMiddle;


import java.util.HashMap;
import java.util.Map;

/*
* 题目描述：
* 给定一个非空的整数数组，返回其中出现频率前 k 高的元素。
示例 1:
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]
示例 2:
输入: nums = [1], k = 1
输出: [1]
提示：
你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。
你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。
题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的。
你可以按任意顺序返回答案。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/top-k-frequent-elements
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
* */
public class 前k个高频元素_347 {
    public static void main(String[] args) {
        前k个高频元素_347 demo = new 前k个高频元素_347();
        int[] nums = new int[] {
                1,1,1,2,2,3
        };
        int[] ints = demo.topKFrequent(nums, 1);
        for(int i : ints){
            System.out.println(i);
        }
    }

    /*
    * 解题思路1 ： 用 Map 记录数组中每个元素出现的个数
    * 然后 根据元素出现的个数对Map中的keys数组进行排序 （升序逆序无所谓）
    * 取出 排序后的 keys数组的前k个元素
    * */
    public int[] topKFrequent(int[] nums, int k) {

        Map<Integer,Integer> map = new HashMap<>();

        for(int i = 0;i<nums.length;i++){
            Integer temp = map.getOrDefault(Integer.valueOf(nums[i]),0);
            map.put(Integer.valueOf(nums[i]),++temp);
        }
        // 对Map进行排序？
        int j = map.size();
        Integer[] keys = map.keySet().toArray(new Integer[j]);
        // 对 keys 进行排序 排序的依据 是 keys 对应的value
        quickSort(keys,0,j-1,map);
        j--;
        int[] result = new int[k];
        for(int i=0; i< k; i++,j--){
            result[i] = keys[j];
        }
        return result;
    }
    // 快排
    void quickSort(Integer[] keys,int left,int right,Map<Integer,Integer> map){
        if(left<right){
            // 计算 中枢点
            int p = getPoint(keys,left,right,map);
            // 根据中枢点 分为两部分 进行快排
            quickSort(keys,left,p-1,map);
            quickSort(keys,p+1,right,map);
        }
    }

    int getPoint(Integer[] keys,int left,int right,Map<Integer,Integer> map){
        int x = map.get(keys[right]);
        // 设置中枢点为最右
        int i = left-1;
        for(int j= left; j <right;j++){
            if(map.get(keys[j]) <= x){
                // 交换
                swap(keys,j,++i);
            }
        }
        swap(keys,++i,right);
        return i;
    }

    void swap(Integer[] keys,int i,int j){
        Integer temp = keys[i];
        keys[i] = keys[j];
        keys[j] = temp;
    }
}
